#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        map<int, int> myMap;
        vector<int> ans;
        myMap[numbers[0]] = 0;        
        for (int i = 1; i < numbers.size(); i++) {
            if (myMap.count(target - numbers[i]) != 0) {
                ans.push_back(myMap[target-numbers[i]]+1);
                ans.push_back(i+1);
                return ans;
            }
            myMap[numbers[i]] = i;
        }
        return ans;
    }
};

// test on online judge http://www.leetcode.com/onlinejudge and all test case passed 

int main(int argc, char **argv)
{
    Solution mySolution;
    vector<int> test;
    int input[] = {2, 7, 11, 15};
    for (int i = 0; i < 4; i++) {
        test.push_back(input[i]);
    }    

    vector<int> ans = mySolution.twoSum(test, 9);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
}
